package binarysorttree;

public class BinarySortTreeDemo {

  public static void main(String[] args) {
    /*
         7
      3     10
    1   5  9   12
  0    2
     */
    int[] arr = new int[]{7,3,10,12,5,1,9,0};
    BinarySortTree binarySortTree = new BinarySortTree();

    for (int i = 0; i < arr.length; i++) {
      binarySortTree.add(new Node(arr[i]));
    }

//    binarySortTree.infixOrder();0 1 3 2 5 7 9 10 12
//    测试删除叶子节点

    binarySortTree.delNode(3);
    binarySortTree.infixOrder();
  }
}

class BinarySortTree{

  Node root;

  public void add(Node node){
    if (root == null){
      root = node;
    }else {
      root.add(node);
    }
  }

  public void infixOrder(){
    if (root != null){
      root.infixOrder();
    }else {
      System.out.println("该二叉树是空的");
    }
  }

  public Node search(int value){
    if (root == null){
      return null;
    }else {
      return root.search(value);
    }
  }

  public Node searchParent(int value){
    if (root == null){
      return null;
    }else {
      return root.searchParent(value);
    }
  }

  public int delRightTreeMin(Node node){
    Node target = node;
    while (target.left != null){
      target = target.left;
    }
    delNode(target.value);
    return target.value;
  }

  public void delNode(int value){
    if (root == null){
      return;
    }else {
      Node targetNode = root.search(value);//待删除的节点
      if (targetNode == null){//找不到要删除的节点
        return;
      }
      if (root.left == null && root.right == null){//说明此时删除的是父节点
        root = null;
        return;
      }

      Node parent = root.searchParent(value);
      if (targetNode.left == null && targetNode.right == null){//要删除的节点是叶子结点
//        判断要删除的节点是父节点的左子节点还是右子节点
        if (parent.left != null && parent.left.value == value){
          parent.left = null;
        }
        if (parent.right != null && parent.right.value == value){
          parent.right = null;
        }
      }else if (targetNode.left != null && targetNode.right != null){//要删除的节点有两个子节点
        int min = delRightTreeMin(targetNode.right);
        targetNode.value = min;
      }else {//要删除的节点有一个子节点
        if (targetNode.left != null){//待删除的节点的左子节点不为空
          if (parent != null){
            if (parent.left.value == value){//待删除的节点是父节点的左子节点
              parent.left = targetNode.left;
            }else {
              parent.right = targetNode.left;//待删除的节点是父节点的右子节点
            }
          }else{
            root = targetNode.left;
          }
        }else {//待删除的节点的右子节点不为空
          if (parent != null){
            if(parent.left.value == value){
              parent.left = targetNode.right;
            }else {
              parent.right = targetNode.right;
            }
          }else {
            root = targetNode.right;
          }
        }
      }
    }
  }
}

class Node{

  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
  }

  @Override
  public String toString() {
    return "Node{" +
            "value=" + value +
            '}';
  }

  public void add(Node node){
    if (node == null){
      return;
    }
    if (node.value < this.value){
      if (this.left == null){
        this.left = node;
      }else {
        this.left.add(node);
      }
    }else {
      if (this.right == null){
        this.right = node;
      }else {
        this.right.add(node);
      }
    }
  }

  public void infixOrder(){
    if (this.left != null){
      this.left.infixOrder();
    }
    System.out.println(this);
    if (this.right != null){
      this.right.infixOrder();
    }
  }

//  查找要删除的节点
  public Node search(int value){
    if (this.value == value){
      return this;
    }else if (value < this.value){
      if (this.left == null){
        return null;
      }
      return this.left.search(value);
    }else {
      if (this.right == null){
        return null;
      }
      return this.right.search(value);
    }
  }
//  查找要删除的节点的父节点
  public Node searchParent(int value){
//    找到了，当前节点就是要找的节点
    if ((this.left != null && this.left.value == value) ||(this.right != null && this.right.value == value)){
      return this;
    }else if (this.left != null && value < this.value){
      return this.left.searchParent(value);
    }else if (this.right != null && value > this.value){
      return this.right.searchParent(value);
    }else {
      return null;
    }
  }
}